\documentclass[12pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}
\input{symboles.sty}


\date{}
\geometry{hmargin=1cm, vmargin=1.5cm}\begin{document}
\title{
Département d'informatique.\\
Partiel de  mathématiques discrètes. \\  
Semestre 2 (Novembre 09)\\ 
}
\maketitle

Aucun document autorisé. 

\begin{tabular}{ll}
Nom: &......................................... \\
Prénom: &.........................................\\ 
\end{tabular}
\section{QCM}
Cette partie contient 30 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\ 

Q. 1. Soit la démonstration  syntaxique suivante: \newline
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration sous hypothèses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ & \_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.& $ \neg \neg B \Rightarrow B $&Axiome 9 ($B/P$).\\
7.& $B$ &mp entre 5. et 6. \\
Conclusion

\end{tabular}
\end{center}

\noindent La démonstration est correcte si en 3. et 4. on a: 
\begin{tabular}{lll}
3.&$A \Rightarrow (\neg B \Rightarrow A)$ &Axiome 1 ($A/P,\neg B /Q$). \\
4.&$\neg B \Rightarrow A $ &modus ponens entre 2. et 3.
\end{tabular}
\\ 

Q. 2. \og $A$ à moins que  $B$ \fg{}
peut-elle être représentée par $ \neg A \Rightarrow B$?
	\\ 

Q. 3.  La négation de \og ce triangle est rectangle donc ce triangle possède un angle droit \fg{}
est-elle  \og ce triangle ne possède pas un angle droit et pourtant il est rectangle\fg{}
	\\ 

Q. 4. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
	Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
\og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
$ p \lor q $?
	\\ 

Q. 5. 
\og Il est faux qu'il ne fait pas froid ou qu'il pleut \fg{}
est-elle équivalente à   \og il fait froid mais il ne pleut pas \fg{}?
	\\ 

Q. 6.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'énoncé suivant est-il une tautologie?
$
(p \Rightarrow q) \land (p \lor r) \Rightarrow q \lor r$.
	\\ 

Q. 7. Une formule propositionnelle $F$ est  conséquence logique d'une antilogie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une tautologie \fg{}?
        \\ 

Q. 8. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
	Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
\og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
$ (p \lor \neg p) \land q $?
	\\ 

Q. 9.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'énoncé suivant est-il une tautologie?
$
(p \Rightarrow q) \lor p \lor r \Rightarrow q \lor r$.
	\\ 

Q. 10. \og $A$ à moins que  $B$ \fg{} 
peut-elle être représentée par $ B \Rightarrow A $?
	\\ 

Q. 11.  L'affirmation \og il fait beau aujourd'hui  donc il ne pleuvra pas dans dix jours \fg{}
est-elle une proposition?
	\\ 

Q. 12. 
Soit la démonstration  syntaxique suivante: \newline
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration sous hypothèses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B $&Axiome 9 ($B/P$).\\
7.& $B$ &mp entre 5. et 6.\\
Conclusion
\end{tabular}
\end{center}

\noindent La démonstration est correcte si en 3. et 4. on a: \newline
\begin{tabular}{lll}
3.&$ (\neg B \Rightarrow \neg A )\Rightarrow (\neg \neg A \Rightarrow  \neg \neg B) $ &théoreme de la contraposée ($\neg B/P, \neg A /Q$) \\
4.&$\neg \neg A \Rightarrow A $ &Axiome 9 ($A/P $).
\end{tabular}
\\ 

Q. 13. \og $A$ à moins que  $B$ \fg{} 
peut-elle être représentée par $ B \lor A $?
	\\ 

Q. 14. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
est-elle suffisante pour affirmer que
\og sa mère est anglaise ou  son père n'est pas français \fg{}?
	\\ 

Q. 15. 
Soit la démonstration  syntaxique suivante: \newline
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration sous hypothèses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B$ &Axiome 9 ($B/P$).\\
7.& $B$ &mp entre 5. et 6.\\
Conclusion
\end{tabular}
\end{center}

\noindent Si elle était complète cela permetrait de
démontrer syntaxiquement
$(\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B)
$.
 L'assertion proposée est vraie ou fausse ?
\\ 

Q. 16.  L'affirmation \og le Vesuve a ravagé la ville de Pompei en 1999 \fg{}
est-elle une proposition?
	\\ 

Q. 17. \og $B$ seulement si  $A$ \fg{}
peut-elle être représentée par $ \neg A \Rightarrow B $?
	\\ 

Q. 18. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une antilogie \fg{}?
        \\ 

Q. 19.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'énoncé suivant est-il une tautologie?
$(p \lor q) \land r \Rightarrow (p \lor r) \land (q \lor r)$.
	\\ 

Q. 20.  La négation de \og ce triangle est rectangle donc ce triangle possède un angle droit \fg{}
est-elle  \og ce triangle n'est pas rectangle donc ce triangle ne possède pas un angle droit \fg{} ?
	\\ 

Q. 21.  Soit $p$ et $q$, deux variables propostionnelles.
	L'énoncé suivant est-il une tautologie?
$
(p \land ( p \lor q)) \Leftrightarrow p$.
	\\ 

Q. 22. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une antilogie \fg{}?
        \\ 

Q. 23. Une formule propositionnelle $F$ est conséquence logique d'une antilogie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une antilogie \fg{}?
        \\ 

Q. 24. 
\og \emph{Si la paix survient, alors il y aura une crise économique
à moins que le pays se dote d'armes nouvelles ou bien exécute
un large programme d'investissement intérieur dans les secteurs de
l'enseignement, de la santé et de la lutte contre la pauvreté.
Il n'est pas possible de se mettre d'accord sur les objectifs
que peut se donner un large programme d'investissement intérieur.
Donc si la paix survient et qu'il n'y a pas de crise économique,
le pays doit se doter d'armes nouvelles.} \fg{}
	 Le raisonnement proposé est-il correct?
        \\ 

Q. 25. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une tautologie \fg{}?
        \\ 

Q. 26. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
est-elle équivalente à
\og sa mère est anglaise ou son père n'est pas français \fg{}?
	\\ 

Q. 27. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  On ne peut donc rien dire de $F$ \fg{}?
        \\ 

Q. 28. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une tautologie \fg{}?
        \\ 

Q. 29.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'énoncé suivant est-il une tautologie?
$(p \lor q) \land r \Leftarrow (p \lor r) \land (q \lor r)$.
	\\ 

Q. 30. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  On ne peut donc rien dire de $F$ \fg{}?
        \\ 

\section{Déduction syntaxique}

Dans le système \og PR \fg{} et en se servant éventuellement des théorèmes 
déjà démontrés dans le cours, démontrer syntaxiquement 
les deux formules propositionnelles suivantes:
\begin{enumerate}
\item
$
  (A \Rightarrow B) \Rightarrow 
  ((A \Rightarrow C) \Rightarrow (A \Rightarrow B \land C))
$

\item 
$
(A \Rightarrow B) \Rightarrow 
((C \Rightarrow \neg B) \Rightarrow  (A \Rightarrow \neg C))
$
\end{enumerate}

\section{Conséquences logiques}
Pour chacun des raisonnements suivants, 
\begin{itemize}
\item réécrire le problème dans une  logique  propositionnelle;
\item dire si la conclusion est une conséquence logique des hypothèses en justifiant.
\end{itemize}

\begin{enumerate}
\item Si je n'étudie pas, j'ai des remords. 
  Mais si je ne vis pas à fond ma jeunesse, j'ai aussi des remords. 
  Or je n'ai pas de remords. 
  C'est donc que j'étudie tout en vivant à fond ma jeunesse.
\item Si Jean n'a pas rencontré Pierre l'autre nuit, 
c'est que Pierre est le meurtrier ou que Jean est un menteur.
Si Pierre n'est pas le meurtrier, alors Jean n'a pas rencontré Pierre 
l'autre nuit et le crime a eu lieu après minuit.
Si le crime a eu lieu après minuit, alors Pierre est 
le meurtrier ou Jean n'est pas un menteur.
Donc Pierre est le meurtrier
\end{enumerate}

\section*{Annexes : Axiomes de PR}

\begin{itemize}\item Axiome 1 : $P\imp (Q\imp P)$
\item Axiome 2 : $(P\imp Q)\imp((P\imp(Q
\imp R))\imp (P\imp R))$
\item Axiome 3 : $P\imp(Q\imp P\et Q)$
\item Axiome 4 : $P\et Q\imp P$
\item Axiome 5 : $P\et Q\imp Q$
\item Axiome 6 : $P\imp P\ou Q$
\item Axiome 7 : $Q\imp P\ou Q$
\item Axiome 8: $(P\imp R)\imp((Q\imp R) \imp(P\ou Q\imp R))$
\item Axiome 9: $\non\non P\imp P$
\item Axiome 10: $(P\imp Q)\imp((P\imp\non Q)$
\item Axiome 11 : $(P\imp Q)\imp((Q\imp P)\imp(P\eqv Q))$
\item Axiome 12 : $(P\eqv Q)\imp(P\imp Q)$
\item Axiome 13 : $(P\eqv Q)\imp(Q\imp P)$
\end{itemize}



\section*{Réponses au QCM}

\begin{large}
\begin{center}
\begin{tabular}{|l|c|c||l|c|c||l|c|c|}
\hline
Numéro & V & F & Numéro & V & F & Numéro & V & F \\ 
\hline
Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\ 
\hline
Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\ 
\hline
Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\ 
\hline
Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\ 
\hline
Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\ 
\hline
Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\ 
\hline
Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\ 
\hline
Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\ 
\hline
Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\ 
\hline
Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\ 
\hline
\end{tabular} 
\end{center}
\end{large}




\end{document}